//#define _CRT_SECURE_NO_WARNINGS 1
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution
//{
//    int ret = INT_MIN;
//    int _maxPathSum(TreeNode* root)
//    {
//        if (root == nullptr) return 0;
//
//        int left = max(0, _maxPathSum(root->left));
//        int right = max(0, _maxPathSum(root->right));
//
//        ret = max(ret, root->val + left + right);
//
//
//        return root->val + max(left, right);
//    }
//public:
//    int maxPathSum(TreeNode* root)
//    {
//        _maxPathSum(root);
//        return ret;
//    }
//};
//
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// * };
// */
//class Solution
//{
//    TreeNode* ans;
//    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q)
//    {
//        if (root == nullptr) return false;
//
//        bool l = dfs(root->left, p, q);
//        bool r = dfs(root->right, p, q);
//
//        if ((l && r) || (root == p || root == q && (l || r)))
//        {
//            ans = root;
//            return true;
//        }
//
//        return l || r || root->val == p->val || root->val == q->val;
//    }
//public:
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
//    {
//        dfs(root, p, q);
//        return ans;
//    }
//};
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution
//{
//    typedef long long LL;
//public:
//    int ans = 0;
//    void _pathsum(TreeNode* root, int targetSum, LL val)
//    {
//        if (root == nullptr) return;
//        if (root->val + val == targetSum)
//        {
//            ans++;
//        }
//        _pathsum(root->left, targetSum, val + root->val);
//        _pathsum(root->right, targetSum, val + root->val);
//    }
//
//    int pathSum(TreeNode* root, int targetSum)
//    {
//        if (root == nullptr) return 0;
//
//        if (root->val == targetSum) ans++;
//        _pathsum(root->left, targetSum, root->val);
//        _pathsum(root->right, targetSum, root->val);
//
//        pathSum(root->left, targetSum);
//        pathSum(root->right, targetSum);
//
//        return ans;
//    }
//};
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//    int preindex = 0;
//public:
//    TreeNode* _BuildTree(vector<int>& preorder, vector<int>& inorder, int left, int right)
//    {
//        if (left > right) return nullptr;
//
//        int preval = preorder[preindex++];
//        TreeNode* root = new TreeNode(preval);
//        int inindex = 0;
//        while (inorder[inindex] != preval) inindex++;
//
//
//        root->left = _BuildTree(preorder, inorder, left, inindex - 1);
//        root->right = _BuildTree(preorder, inorder, inindex + 1, right);
//
//        return root;
//    }
//
//    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
//    {
//        return _BuildTree(preorder, inorder, 0, preorder.size() - 1);
//    }
//};
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    void flatten(TreeNode* root)
//    {
//        stack<TreeNode*> st;
//        if (root) st.push(root);
//        while (!st.empty())
//        {
//            TreeNode* tmp = st.top();
//            st.pop();
//            if (tmp->right) st.push(tmp->right);
//            if (tmp->left) st.push(tmp->left);
//            tmp->left = nullptr;
//            if (!st.empty())tmp->right = st.top();
//        }
//    }
//};
//
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution
//{
//public:
//
//    vector<int> rightSideView(TreeNode* root)
//    {
//        vector<int> ret;
//        queue<TreeNode*> q;
//        if (root) q.push(root);
//        while (!q.empty())
//        {
//            int sz = q.size();
//            while (sz--)
//            {
//                TreeNode* tmp = q.front();
//                q.pop();
//                if (sz == 0)
//                {
//                    ret.push_back(tmp->val);
//                }
//
//                if (tmp->left) q.push(tmp->left);
//                if (tmp->right) q.push(tmp->right);
//            }
//        }
//
//        return ret;
//    }
//};